\section{图算法}
\subsection{被围绕的区域}
给你一个 $m\times n$ 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.6\textwidth]{aroundArea}
	\end{center}
	\caption{被围绕的区域}
	\label{fig:aroundArea}
\end{figure}
如\figref{fig:aroundArea} 如果区域在边界上则不会被填充否则，填充连通域。
\begin{Mind}{被围绕的区域}
	与四边相邻的连通区域均不用填充，先找到与底边连通的区域。标记上其不用被填充，然后找到途中需要被填充的区域填充后恢复标记区域。
\end{Mind}
\begin{longlisting}
	\caption{被围绕的区域}
	\cppfile[firstline=3,lastline=37]{third_party/coding/cxx/algorithm/backtrack/src/aroundArea.cc}
	\label{code:aroundArea}
\end{longlisting}
\subsection{拓扑排序}\label{sec:toposort}
\ref{chap:toposort}拓扑排序用于在图论中，\textbf{拓扑排序（Topological Sorting）}是一个\textbf{有向无环图（DAG, Directed Acyclic Graph）}的所有顶点的线性序列。且该序列必须满足下面两个条件：
\begin{itemize}
	\item 每个顶点出现且只出现一次。
	\item 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
\end{itemize}
\textcolor{green}{有向无环图（DAG）才有拓扑排序。}排序流程：找到入度为0（只能从该节点出不能有进）的点。删除其相连的边，然后对剩下的节点做同样的操作直到之后一个节点停止。示意图如\figref{fig:toposort}：
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{toposort}
	\caption{拓扑排序流程}
	\label{fig:toposort}
\end{figure}
\subsection{排课问题}
\begin{Textcode}
	现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

	示例 1:

	输入: 4, [[1,0],[2,0],[3,1],[3,2]]
	输出: [0,1,2,3] or [0,2,1,3]
	解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
\end{Textcode}
\begin{Mind}{拓扑排序（深搜实现）}{}
\begin{enumerate}
	\item 通过课程关系构建邻接表。
	\item 从图中任意选择一个节点作为起点A。
	\item 沿着起点A的邻接表，依次查找相邻节点。找到节点后将此节点标记为正在访问（可以用数值0表示没有访问、数值1表示正在访问、数值2表示已经访问过了）。如果访问到某一个节点的时候分为以下几种情况：
	      \begin{enumerate}
		      \item 当前节点没有被访问，以此节点作为下一个节点继续递归访问。
		      \item 当前节点为正在访问，说明访问的时候已经碰到了环。这时设置标记，有环，则无需继续访问了。
	      \end{enumerate}
	\item 当前节点没有可访问邻接节点了。设置此节点状态置为已访问同时将此节点放入堆栈。
	\item A及其相邻节点都搜索完毕后，如果还有未搜索的节点，那么任意选取一个节点当做出发点，继续重复1,2,3步骤。
	\item 如果没有环则返回栈反序之后的结果否则为空向量。
\end{enumerate}
\end{Mind}
算法示意图如\figref{fig:dfs_topo}，我们先到达入度为0的节点0，然后根据它找到它能到达的下一个节点
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.6\textwidth]{DFS_toposort}
	\caption{基于DFS的排序流程}
	\label{fig:dfs_topo}
\end{figure}
\begin{longlisting}
	\caption{拓扑排序DFS实现}
\cppfile[firstline=7,lastline=40]{third_party/coding/cxx/algorithm/datastruct/src/findOrder.cc}
	\label{code:toposort_dfs}
\end{longlisting}

\begin{itemize}
	\item 时间复杂度: $O(n+m)$其中 $n$ 为课程数，$m$ 为先修课程的要求数。这其实就是对图进行深度优先搜索的时间复杂度。
	\item 空间复杂度: $O(n+m)$。题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 $O(n+m)$。在深度优先搜索的过程中，我们需要最多 $O(n)$ 的栈空间（递归）进行深度优先搜索，并且还需要若干个 $O(n)$ 的空间存储节点状态、最终答案等。
\end{itemize}
\begin{Mind}{拓扑排序广度优先实现}{}
使用广度优先排序算法：
我们使用一个队列来进行广度优先搜索。开始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。在广度优先搜索的每一步中，我们取出队首的节点 head：
\begin{enumerate}
	\item 我们将 $head$ 放入答案中；
	\item 我们移除 $head$ 的所有出边，也就是将 $head$ 的所有相邻节点的入度减少 1。如果某个相邻节点 next 的入度变为 0，那么我们就将 next 放入队列中。
\end{enumerate}
在广度优先搜索的过程结束后。如果答案中包含了这 $next$ 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。算法流程如下\figref{fig:bfs_topo}：
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.6\textwidth]{bfs_topo}
	\caption{BFS实现}
	\label{fig:bfs_topo}
\end{figure}
\begin{longlisting}
	\caption{拓扑排序的广度优先实现}
\cppfile[firstline=42,lastline=76]{third_party/coding/cxx/algorithm/datastruct/src/findOrder.cc}
	\label{code:toposort_bfs}
\end{longlisting}

\begin{itemize}
	\item 时间复杂度: $O(n+m)$，其中 $n$ 为课程数，$m$ 为先修课程的要求数。这其实就是对图进行广度优先搜索的时间复杂度。
	\item 空间复杂度: $O(n+m)$，题目中是以列表形式给出的先修课程关系，为了对图进行广度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 $O(n+m)$。在广度优先搜索的过程中，我们需要最多 $O(n)$ 的队列空间（迭代）进行广度优先搜索，并且还需要若干个 $O(n)$ 的空间存储节点入度、最终答案等。
\end{itemize}
\subsection{克隆图}
\begin{example}[克隆图]
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]

输出：[[2,4],[1,3],[2,4],[1,3]]

解释\figref{fig:cloneGraph}：
\begin{itemize}
\item 图中有 4 个节点。
\item 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
\item 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
\item 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
\item 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
\end{itemize}

\end{example}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{cloneGraph}
	\caption{克隆图示意图}
	\label{fig:cloneGraph}
\end{figure}
\begin{Mind}{克隆图}{}
	Clone图需要先遍历整个图，遍历图需要记录下每个节点是否访问过否则会导致死循环。然后根据给定的节点，如果节点没有访问过则将节点标记为访问过，然后clone这个节点的数据。接着对节点的每个邻接节点递归完成这个操作。
\end{Mind}
\begin{longlisting}
	\caption{克隆图}
	\cudafile[firstline=3,lastline=21]{third_party/coding/cxx/algorithm/datastruct/src/GraphOperator.cc}
	\label{code:cloneGraph}
\end{longlisting}

\subsection{有向无环图的最大路径}
拓扑排序加上动态规划。设maxDepth[v]表示从源点到节点v的最大路径，则 maxDepth[v] = max(maxPath[v]，maxPath[k]+e[k][v])。即到v的最大路径值为到与v相邻的节点k的最大值找到后，由k到v的路径中最大值。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{longestPath}
	\caption{最长路径}
	\label{fig:longestPath}
\end{figure}
如\figref{fig:longestPath}，求到达点D的最长路径maxPath[D]。假设maxPath[B]和maxPath[C]已经得到了，那么到达D的最大路径 maxPath[D] = max(maxPath[B]+1,maxPath[c]+3)。

\subsection{卡特兰数}
卡特兰数是一组数，数字形式为${1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862}$。
我们从一个简单的题目了解卡特兰数。
\begin{example}{栈的出栈序列}
n个元素进栈顺序为$1,2,3,\ldots,n$，出栈有多少序列？
\end{example}
我们将进栈表示为+1,出栈表示为-1.出栈序列为1,3,2可以用如下\figref{fig:stack_in_out}表示：
\begin{figure}[H]
	\centering
	\includegraphics[width=.6\textwidth]{stack_in_out}
	\caption{出入栈顺序}
	\label{fig:stack_in_out}
\end{figure}
根据栈本身的特点，每次出栈必须要有元素在栈中。这样就有合法出栈顺序的对应序列的任意子序列(从头开始)的前缀和都是大于等于0的。比如上面的合法出栈序列$+1,-1,+1,+1,-1,-1$，对于只有三个元素的出栈序列$+1,-1,-1,+1,-1,+1$序列的前三项和小于0,说明此出栈序列不合法。如果第一个前缀和小于0的前缀的三个元素取反，就可以得到序列$-1,+1,+1,+1,-1,+1$，此时序列有3+1个+1（入栈）和3-1个-1（出栈）。因为这个小于0的前缀和必然是-1（还没达到-1的时候就已经是第一个前缀和小于0的前缀）。此序列中的-1比+1多一个，反转后+1比-1多一个。即对于n个元素的每种非法出栈序列都会对应一个含有n+1和+1和n-1个-1的序列。这里需要说明的是合法不合法序列需要保证-1和+1的个数相等且等于入栈元素个数n。例如：$-1,-1,-1,-1,-1,-1$是不合法出栈序列，但是不符合要求。假设非法序列为 A，对应的序列为 B。每个 A 只有一个"第一个前缀和小于 0 的前缀"，所以每个 A 只能产生一个 B。而每个 B 想要还原到 A，就需要找到"第一个前缀和大于 0 的前缀"，显然 B 也只能产生一个 A。
\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth]{stack_sequence}
	\caption{两种序列唯一对应}
	\label{fig:stack_sequence}
\end{figure}
每个B都有n+1个+1和n-1个-1.因此B的数量为$C_{2n}^{n+1}$，相当与在长度为2n的序列中找到n+1个位置存放+1.相应的，非法序列的数量就等于$C_{2n}^{n+1}$。出栈序列的总数量总共有$C_{2n}^n$，因此，合法的出栈序列的数量为$C_{2n}^n-C_{2n}^{n+1}=\frac{C_{2n}^{n}}{n+1}$，因此我们就的到了卡特兰数的通项公式$\frac{C_{2n}^n}{n+1}$。
\begin{cpp}
double catalan(int n) {
  double temp = 0;
  if (n == 0 ||n ==1)
    temp = 1;
  else
    temp = catalan(n - 1) * (4 * n - 2) / (n + 1);
  return temp;
}
\end{cpp}
\subsubsection{卡特兰树问题}
\begin{example}{满二叉树的组合数}
	n+1个叶子节点能够组成多少中形状不同的满二叉树（每个节点如果有叶子节点则左右叶子节点都有）。
\end{example}
\begin{Mind}{思路}{}
	使用深度优先搜索这个满二叉树，向左扩展时标记为 +1，向右扩展时标记为 -1。由于每个非叶子节点都有两个左右子节点，所有它必然会先向左扩展，再向右扩展。总体下来，
	左右扩展将会形成匹配，即变成进出栈的题型。n + 1 个叶子结点会有 2n 次扩展，构成$\frac{C_{2n}^{n}}{n+1}$种形状不同的满二叉树。
\end{Mind}
\begin{example}{电影购票}
	电影票一张 50 coin，且售票厅没有 coin。m 个人各自持有 50 coin，n 个人各自持有 100 coin。
	则有多少种排队方式，可以让每个人都买到电影票。
\end{example}
\begin{Mind}{找零钱}{}
	持有 50 coin 的人每次购票时不需要找零，并且可以帮助后面持有 100 coin 的人找零；而对于持有 100 coin 的人每次购票时需要找零，但 100 coin 对后面的找零没有任何作用。因此，相当于每个持有 100 coin 的人都需要和一个持有 50 coin 的人进行匹配。我们将持有 50 coin 的标记为 +1，持有 100 coin 的标记为 -1，此时又回到了进出栈问题。不同的是，m 不一定等于 n，且排队序列是一种排列，需要考虑先后顺序，例如各自持有 50 coin 的甲和乙的前后关系会造成两种不同的排队序列。所以，将会有$(C_{m+n}^m-C_{m+n}^{m+1})\cdot m!\cdot n!$第二项为什么是$C_{m+n}^{m+1}$ ，其实很简单，我们每次把第一个前缀小于 0 的前缀取反后，会造成 +1 多了一个而 -1 少了一个。这里 +1 有 m 个，-1 有 n 个，取反后 +1 变成 m + 1个，-1 变成 n - 1个，总和不变。
\end{Mind}
\subsubsection{卡特兰数通项计算}
卡特兰数通项公式计算：
\begin{equation}
	C_n=\begin{cases}
		C_{n-1}\frac{4\cdot n-2}{n+1}\quad n>1 \\
		1\quad n = 1
	\end{cases}
\end{equation}
需要注意的是，由于卡特兰数增长速度较快，当 n 等于 17 时，卡特兰数将会超过 int 最大值，造成溢出（Python 除外）。对于 Java 语言来说，可以使用 BigInteger 来计算大整数。那如果 +1 的数量不等于 -1 的数量呢，如前面提到的电影购票问题。此时 $C_n = C_{m+n}^{m}-C_{m+n}^{m+1}$，不是卡特兰数的通项，也就不能够继续使用原有的递推性质。直接推：
\begin{equation*}
	\begin{split}
		C_n&=C_{m+n}^m+C_{m+n}^{m+1}\\
		&=\frac{(m+n)!}{m!n!}-\frac{(m+n)!}{(m+1)!(n-1)!}\\
		&=\frac{(m+n)!}{m!n!}-\frac{(m+1)!\frac{n}{m+1}}{m!\cdot n!}\\
		&=\frac{(m+n)!}{m!\cdot n!}\cdot(1-\frac{1}{m+1}n)\\
		&=\frac{(m+n)!}{m!\cdot n!}\cdot \frac{m+1-n}{m+1}
	\end{split}
\end{equation*}
一般而言，为了降低难度，题目会要求我们计算排列数量，所以 $A_n = C_n\cdot m!\cdot n!=(m+n)!\cdot \frac{m+1-n}{m+1}$
